package com.zzy.algorithm.tree;

import com.zzy.algorithm.model.QueueNode;
import com.zzy.algorithm.model.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * LeetCode - 101 ： 二叉树最大深度
 *
 * 给定一个二叉树，找出其最大深度。
 *
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 */
public class Q22_DeepestOfBinaryTree {

    public static void main(String[] args) {
        Q22_DeepestOfBinaryTree q22_deepestOfBinaryTree = new Q22_DeepestOfBinaryTree();
//        int solution = q22_deepestOfBinaryTree.solution(TreeNode.treeNode1);
        int solution = q22_deepestOfBinaryTree.solution2(TreeNode.treeNode1);
        System.out.println("solution = " + solution);
    }

    private int solution(TreeNode root){
        if(root == null){
            return 0;
        }
        return Math.max(solution(root.left),solution(root.right)) + 1;
    }


    private int solution2(TreeNode treeNode){
        if(treeNode == null){
            return 0;
        }
        Queue<QueueNode> queue = new LinkedList<>();
        QueueNode queueNode = new QueueNode(treeNode,1);
        queue.offer(queueNode);
        int maxDeep = 1;
        while(!queue.isEmpty()){
            QueueNode node = queue.poll();
            maxDeep = Math.max(maxDeep,node.deep);
            if(node.treeNode.left != null){
                queue.offer(new QueueNode(node.treeNode.left,node.deep+1));
            }
            if(node.treeNode.right != null){
                queue.offer(new QueueNode(node.treeNode.right,node.deep+1));
            }
        }
        return maxDeep;
    }














//    if(node == null){
//        return 0;
//    }
//    Queue<QueueNode> queue = new LinkedList<>();
//        queue.offer(new QueueNode(node,1));
//    int max = 1;
//        while(!queue.isEmpty()){
//        QueueNode queueNode = queue.poll();
//        if(queueNode.treeNode.left == null && queueNode.treeNode.right == null){
//            max = Math.max(max,queueNode.deep);
//        }
//        if(queueNode.treeNode.left != null){
//            queue.offer(new QueueNode(queueNode.treeNode.left,queueNode.deep+1));
//        }
//        if(queueNode.treeNode.right != null){
//            queue.offer(new QueueNode(queueNode.treeNode.right,queueNode.deep+1));
//        }
//    }
//        return max;

}
